package HighMethod04;

import java.util.Stack;

//高度平衡二叉树  可以和红黑树对比
class AVLTree {
    class AVLNode {
        AVLNode leftchild;
        AVLNode parent;
        AVLNode rightchild;
        int balance; // -1 ,0 , 1 平衡因子
        int key;

        public AVLNode() {

        }
        public AVLNode(int x) {
            leftchild = rightchild = parent = null;
            key = x;
            balance = 0;
        }

    }

    AVLNode root;
    AVLNode cur;

    public AVLTree() {
        root = null;
        cur = null;
    }

    //左单旋转
    private void RotateLeft(AVLNode ptr) {
        AVLNode newroot = ptr.rightchild;
        newroot.parent = ptr.parent;//1
        ptr.rightchild = newroot.leftchild;
        if (newroot.leftchild != null) {
            newroot.leftchild.parent = ptr;//2
        }
        newroot.leftchild = ptr;
        AVLNode pa = ptr.parent;
        if (pa == null) {
            root = newroot;
        } else {
            if (pa.leftchild == ptr) {
                pa.leftchild = newroot;
            } else {
                pa.rightchild = newroot;
            }
        }
        ptr.parent = newroot; // 3
    }

    //右单旋转
    private void RotateRight(AVLNode ptr) {
        AVLNode newroot = ptr.leftchild;    //1
        newroot.parent = ptr.parent;
        ptr.leftchild = newroot.rightchild; //2
        if (newroot.rightchild != null) {
            newroot.rightchild.parent = ptr;
        }
        newroot.rightchild = ptr;   //3
        AVLNode pa = ptr.parent;
        if (pa == null) {
            root = newroot;
        } else {
            if (pa.leftchild == ptr) {
                pa.leftchild = newroot;
            } else {
                pa.rightchild = newroot;
            }
        }
        ptr.parent = newroot;   //4

    }

    //左平衡函数
    private void LeftBalance(AVLNode ptr) {
        AVLNode leftSub = ptr.leftchild;    //节点B
        AVLNode rightSub = null;        //节点E

        switch (leftSub.balance) {       //对节点B的平衡因子分三种情况，第三种情况又分了三种
            case 0:         //本身就是平衡的
                System.out.println("left balanced！");
                break;
            case -1:        //插入在D节点处时，B的平衡因子是-1，要右单旋转
                ptr.balance = 0;
                leftSub.balance = 0;
                RotateRight(ptr);
                System.out.println("左平衡-1");
                break;
            case 1:         //插入在F、G节点处 B的平衡因子都是1，要对B的rightchild.balance（rightSub.balance） switch更新平衡因子
                rightSub = leftSub.rightchild;
                switch (rightSub.balance) {
                    case 1:
                        ptr.balance = 0;
                        leftSub.balance = -1;
                        System.out.println("左平衡1 1");
                        break;
                    case 0:
                        ptr.balance = 0;
                        leftSub.balance = 0;
                        System.out.println("左平衡1 0");
                        break;
                    case -1:
                        ptr.balance = 1;
                        leftSub.balance = 0;
                        System.out.println("左平衡1 -1");
                        break;
                }
                rightSub.balance = 0;
                RotateLeft(leftSub);        //以节点E为跟进行左单旋转
                RotateRight(ptr);           //以变换为之后的节点E为根进行右单旋转
                break;
        }
    }

    //右平衡函数，与左平衡函数镜像
    private void RightBalance(AVLNode ptr) {
        AVLNode rightSub = ptr.rightchild;    //节点B
        AVLNode leftSub = null;        //节点E

        switch (rightSub.balance) {       //对节点B的平衡因子分三种情况，第三种情况又分了三种
            case 0:         //本身就是平衡的
                System.out.println("right balanced！");
                break;
            case 1:        //插入在D节点处时，B的平衡因子是-1，要右单旋转
                ptr.balance = 0;
                rightSub.balance = 0;
                RotateLeft(ptr);
                System.out.println("右平衡-1");
                break;
            case -1:         //插入在F、G节点处 B的平衡因子都是1，要对B的rightchild.balance（rightSub.balance） switch更新平衡因子
                leftSub = rightSub.rightchild;
                switch (leftSub.balance) {
                    case 1:
                        ptr.balance = -1;
                        rightSub.balance = 0;
                        System.out.println("右平衡1 1");
                        break;
                    case 0:
                        ptr.balance = 0;
                        rightSub.balance = 0;
                        System.out.println("右平衡1 0");
                        break;
                    case -1:
                        ptr.balance = 0;
                        rightSub.balance = 1;
                        System.out.println("右平衡1 -1");
                        break;
                }
                leftSub.balance = 0;
                RotateRight(rightSub);        //以节点E为跟进行左单旋转
                RotateLeft(ptr);           //以变换为之后的节点E为根进行右单旋转
                break;
        }
    }

    private void Adjust_AVL(AVLNode ptr) {
        AVLNode pa = ptr.parent;
        boolean high = true;
        while (high && pa != null) {
            if (pa.leftchild == ptr) {
                switch (pa.balance) {
                    case 0:
                        pa.balance = -1;
                        break;
                    case 1:
                        pa.balance = 0;
                        high = false;
                        break;
                    case -1:
                        LeftBalance(pa);
                        high = false;
                        break;
                }
            } else {
                switch (pa.balance) {
                    case 0:
                        pa.balance = 1;
                        break;
                    case -1:
                        pa.balance = 0;
                        high = false;
                        break;
                    case 1:
                        RightBalance(pa);
                        high = false;
                        break;
                }
            }
            ptr = pa;
            pa = ptr.parent;
        }
    }

    //这里还需要debug,暂时没bug
    public boolean Insert(int kx) {
        boolean res = true;
        if (root == null) {
            //根节点为空，就创建为根节点，返回true
            root = new AVLNode(kx);
            return res;
        }
        //如果根节点不为空，cur作为遍历节点，即标记
        cur = root;
        //记录前一个节点
        AVLNode pa = null;
        while (cur != null && cur.key != kx) {
            pa = cur;
            cur = kx < cur.key ? cur.leftchild : cur.rightchild;
        }
        //如果找到了(&& cur.key == kx)，就不能插入，返回false
        if (cur != null) {
            res = false;
        } else {
            //没有找到，就创建一个新节点
            cur = new AVLNode(kx);
            cur.parent = pa;
            if (cur.key < pa.key) {
                //如果比父节点小，就作为左儿子
                pa.leftchild = cur;
            } else {
                //如果比父节点大，就作为右儿子
                pa.rightchild = cur;
            }
        }
        Adjust_AVL(cur);

        return res;
    }

    //删除节点
    private void delete() {

    }

    //非递归遍历二叉高度平衡树
    public void NiceInOrder() {
        if (root == null) return;
        Stack<AVLNode> st = new Stack<>();
        cur = root;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.leftchild;
            }
            cur = st.pop();
            System.out.print(cur.key + " ");
            cur = cur.rightchild;
        }
        System.out.println();
    }

    //非递归，先序遍历
    public void NicePreOrder() {
        if (root == null) return;
        Stack<AVLNode> st = new Stack<>();
        st.push(root);
        while (!st.empty()) {
            AVLNode ptr = st.peek();
            st.pop();
            System.out.print(ptr.key + " ");
            if (ptr.rightchild != null) {
                st.push(ptr.rightchild);
            }
            if (ptr.leftchild != null) {
                st.push(ptr.leftchild);
            }
        }
        System.out.println();
    }
}


public class test01 {
    public static void main(String[] args) {
//                                                          *   *
        int[] ar = {53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88, 92};
/**                     53
 *              17               87
 *          9       45       65       92
 *                23           81   88  94
 *                            78
 *
 */
        System.out.println("创建AVL树-------！");

        AVLTree avlTree = new AVLTree();
        for (int i = 0; i < ar.length; i++) {
            avlTree.Insert(ar[i]);
        }

        System.out.println("中序遍历结果如下:");
        avlTree.NiceInOrder();

        System.out.println("先序遍历结果如下:");
        avlTree.NicePreOrder();
    }
}
